1. Field of the Invention
The invention concerns the graphical display of information and more particularly concerns the graphical display of directed graphs.
2. Description of the Prior Art
Directed graphs (digraphs) are a common way of representing hierarchical or asymmetric relationships among elements from a set. Digraphs arise naturally in descriptions of processes and work flows, control flow and data dependencies in computer software, in representations of finite state machines, and other applications. Layouts or drawings of graphs can help to make graphs more understandable by revealing their structure. For this reason hand-drawn layouts are often used in documentation. The problem is that manual graph layout is tedious and difficult. This has lead to the invention of automatic layout programs. Here, the user creates a specification of nodes and edges for input to the layout generator. The specification may be entered through a text editing program or may be created by means of utility programs that extract graph specifications from other forms of data such a program source code. The specification does not necessarily contain any geometric coordinates. The layout system then reads this specification, executes algorithms to determine node and edge coordinates, and generates a graphics file which contains a representation of the drawing of the graph. The file may be transmitted to a computer screen for display or to a printer for printing, or saved on an external storage device for future use.
Often, nodes in graphs of complex systems can be classified into subgraphs. We use the term "cluster" to refer to node-induced subgraphs that are drawn in the layout using a box to outline the nodes of the cluster. This box may not contain any nodes not in the cluster. We will assume that the classification of nodes into clusters is performed either by the user or by an external utility or by any other appropriate technique. Typically the classification depends on either application-dependent information, or on syntactical properties of the graph. If this decomposition is recursive, then the clusters are nested. For example, process decomposition diagrams from formal methods in software engineering can exhibit such structure. (See Harry S. Delugach, "Specifying Multiple-Viewed Software Requirements with Conceptual Graphs", Journal of Systems Software 19, pp. 207-224, 1992; Robert W. Krut, Jr. and David P. Wood, "Evaluation of Process Modeling Improvements", Technical Report CMU/SEI-91-TR5, Software Engineering Institute, Carnegie-Mellon University, April 1991.)
The most salient previous work in this area is the "compound graph" layout technique of Sugiyama and Misue (see "Visualization of Structural Information: Automatic Drawing of Compound Digraphs", IEEE Transactions on Systems, Man, and Cybernetics SMC-12:4, pp. 876-892, July 1991.) This is a collection of heuristics for drawing digraphs with nested clusters. The technique supports not only layout of simple or conventional node-to-node edges, but also "compound" i.e. node-to-cluster and cluster-to-cluster edges as seen in FIG. 11. The Edge system of Newbery and Tichy also handles nested layouts by straightforward recursion (see Frances Newbery Paulish and Walter F. Tichy, "EDGE: An Extendible Graph Editor," Software: Practice and Experience, 20:S1, pp. 1/63-S1/88, 1990; also Frances Newbery Paulisch, The design of an extendible graph editor, Ph.D. thesis, University of Karlsruhe, January 1992.) A graph from this work is depicted in FIG. 13. Messinger et al implemented a recursive layout technique in the Compoze system. Here the main objective was to improve performance, thus clusters are an data structure, but not explicitly drawn in the output (see E. B. Messinger, L. A. Rowe and R. H. Henry, "A Divide-and-Conquer Algorithm for the Automatic Layout of Large Directed Graphs," IEEE Transactions on Systems, Man and Cybernetics, SMC-21:1, pp. 1-12, 1991.) Such internal clusters are noticeable in the layout of FIG. 12, which is from their work. Brown and Gargiulo describe a technique of making nested graph layouts according to somewhat different aesthetic criteria than ours, employing a nested box notation to replace edges and thereby reduce clutter in layouts (see P. Brown and T. Gargiulo, "An Object Oriented Layout for Directed Graphs", Proc. IEEE Symposium on Assessment of Quality Software Development Tools, pp. 164-171, May 1992).
There are similarities between directed graph layout and circuit layout (VLSI or board level), but there is a fundamental difference. In either case the user specifies the components and their interconnections. The system then determines the placement of components and the routing of interconnections. The difference is in the kind objective functions that measure layout quality. The objective of graph visualization is to assist human understanding of graph data. For circuit layout the objective is to optimize circuit performance by reducing critical path delays, power consumption, layout area, etc. These lead to vastly different layout styles. For further discussion of readability of graph layouts and related diagrams, we refer to Eades et al (P. Eades and R. Tamassia, "Algorithms for Drawing Graphs: An Annotated Bibliography," Brown University Dept. of Computer Science, Technical Report CS-09-89, 1989. An updated version is available as a PostScript file by anonymous ftp to wilma.cs.brown.edu in pub/gdbiblio.ps.Z. See also P. Eades and L. Xuemin, "How to Draw a Directed Graph," Proc. IEEE Workshop on Visual Languages (VL '89), pp. 13-17, 1989.)
As is apparent from the foregoing discussion, the layout of directed graphs which are to be read by human beings must take into account readability, aesthetics, and compactness of representation. It is an object of the invention disclosed herein to automatically produce directed graphs which are more readable, better looking, and more compact than those proviced by the prior art.